package Review;

import com.sun.xml.internal.bind.v2.model.core.EnumLeafInfo;
import javafx.scene.SceneAntialiasing;
import org.omg.CORBA.ORB;
import org.w3c.dom.ls.LSException;
import sun.reflect.generics.tree.Tree;
import sun.security.jgss.HttpCaller;
import sun.security.util.DerOutputStream;

import javax.swing.plaf.PanelUI;
import javax.xml.transform.sax.SAXTransformerFactory;
import java.util.*;

public class TextBinaryTree2 {
    static class TreeNode {
        public char value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char value) {
            this.value = value;
        }
    }

    //定义二叉树的根节点
    public TreeNode root;

    //非正规创建一颗二叉树
    public TreeNode createTree() {
        TreeNode A = new TreeNode('a');
        TreeNode B = new TreeNode('b');
        TreeNode C = new TreeNode('c');
        TreeNode D = new TreeNode('d');
        A.left = B;
        A.right = C;
        B.left = D;
        return A;//A就是根节点
    }

    //前序遍历
    public void preorder(TreeNode root) {
        if (root == null) return;
        System.out.println(root.value);
        preorder(root.left);
        preorder(root.right);
    }

    //中序遍历二叉树
    public void inorder1(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.println(root.value);
        inorder(root.right);
    }

    //后序遍历二叉树
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.value);
    }

    //前序遍历有返回值 此时list需要放在外面，否则每次递归都会产生一个新的list
    List<Character> list = new LinkedList<>();

    public List<Character> preorderTraversal(TreeNode root) {
        if (root == null) return list;
        list.add(root.value);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }

    //中序遍历二叉树有返回值
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) return list;
        List<Character> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);
        list.add(root.value);
        List<Character> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }

    //二叉树的后序遍历有返回值
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list = new LinkedList<>();
        if (root == null) return list;
        List<Character> leftTree = postorderTraversal(root.left);
        list.addAll(leftTree);
        List<Character> rightTree = new LinkedList<>();
        list.addAll(rightTree);
        list.add(root.value);
        return list;
    }

    //获取二叉树中的节点的个数
    public int size(TreeNode root) {
        if (root == null) return 0;
        return size(root.left) + size(root.right) + 1;
    }

    //获取二叉树的节点 遍历思路
    public int count;

    public int size1(TreeNode root) {
        if (root == null) return 0;
        count++;
        size1(root.left);
        size1(root.right);
        return count;
    }
    //获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    //遍历思路   叶子节点的特点就是没有左右孩子，所以只要没有左右孩子的节点在二叉树中就是叶子节点
    public int leafCount;
    public void leafCount(TreeNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null) leafCount++;
        leafCount(root.left);
        leafCount(root.right);
    }
    //获取第K层的节点个数
    //求第k层的节点个数就相当于求第k-1层的孩子的节点个数
    public int getLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        int leftTree = getLevelNodeCount(root.left, k-1);
        int rightTree = getLevelNodeCount(root.right, k-1);
        return leftTree + rightTree;
    }
    //获取二叉树的高度
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
    //二叉树的层序遍历 使用先进先出的数据结构：队列
    public void leveOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur.value + " ");
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
        }
    }
    //二叉树的层序遍历有返回值
    public List<List<Character>> levelOrder1(TreeNode root) {
        List<List<Character>> list = new LinkedList<>();
        Queue<TreeNode> queue =new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Character> ret = new LinkedList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                ret.add(cur.value);
                size--;
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            list.add(ret);
        }
        return list;
    }
    //判断二叉树中是否存在key值
    public TreeNode find(TreeNode root, int key) {
        if (root == null) return null;
        if (root.value == key) return root;
        TreeNode leftTree = find(root.left, key);
        if (leftTree != null) return leftTree;
        TreeNode rightTree = find(root.right, key);
        if (rightTree != null) return rightTree;
        return null;
    }
    //相同的树  时间复杂度O(min(m, n))  空间复杂度(O(m, n))
    public boolean isSameTree(TreeNode root1, TreeNode root2) {
        //一个为空 一个不为空
        if (root1 == null && root2 != null ||
                root1 != null && root2 == null) return false;
        //两个都是空
        if (root1 ==null && root2 == null) return true;
        //两个都不为空
        if (root1.value != root2.value) return false;
        //递归判断左子树和右子树（左子树和右子树都相同的情况才算是俩颗相同的树）
        boolean leftTree = isSameTree(root1.left, root2.left);
        boolean rightTree = isSameTree(root1.right, root2.right);
        return  leftTree && rightTree;
    }
    //另一颗树的子树 时间复杂度：O(S * T) 空间复杂度：O(max（SHeight，THeight）)
    public boolean isChildTree(TreeNode root1, TreeNode subRoot) {
        if (isSameTree(root1, subRoot)) return true;
        boolean leftTree = isSameTree(root1.left, subRoot);
        boolean rightTree = isSameTree(root1.right, subRoot);
        return leftTree || rightTree;
    }
    //反转一颗二叉树
    public TreeNode reverseTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        reverseTree(root.left);
        reverseTree(root.right);
        return root;
    }
    //判断一棵树是否为平衡二叉树
    /*分别求左子树和右子树的高度，之后左子树的高度和右子树的高度差不能超过1
    * 才算是平衡二叉树*/
    public boolean isBalanceTree(TreeNode root) {
        if (root == null) return true;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.abs(leftHeight-rightHeight) < 2 &&
                isBalanceTree(root.left) && isBalanceTree(root.right);
    }
    //在O（n）的时间复杂度内判断一颗树是否是平衡二叉树
    /*在求二叉树的高度的过程中就判断是否满足平衡二叉树*/
    public int getHeight2(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight2(root.left);
        if (leftHeight < 0) return -1;
        int rightHeight = getHeight2(root.right);
        if (rightHeight < 0) return -1;
        if (Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight, rightHeight) + 1;
        }else {
            return -1;
        }
    }
    //对称二叉树 判断左子树和右子树是否为对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isChildSymmetric(root.left, root.right);
    }
    private boolean isChildSymmetric(TreeNode rootL, TreeNode rootR) {
        if (rootL == null && rootR != null ||
                rootL != null && rootR ==null) return false;
        if (rootL == null && rootR == null) return true;
        //左树和右树都不为空就判断值是否相等
        if (rootL.value != rootR.value) return false;
        return isChildSymmetric(rootL.left, rootR.right) &&
                isChildSymmetric(rootL.right, rootR.left);
    }
    //二叉树的层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur.value + " ");
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
        }
    }
    //二叉树层序遍历有返回值
    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        while (!queue.isEmpty()) {
            List<Character> ret = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {
                TreeNode cur = queue.poll();
                ret.add(cur.value);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            list.addAll(Collections.singleton(ret));
        }
        return list;
    }
    //二叉树的构造及遍历：读入一颗先序遍历的字符串，创建一颗二叉树
    /*然后按中序遍历输出二叉树的节点。 但是也是可以创建出一颗二叉树的（有顺序的前序遍历）*/
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        TreeNode root = createTree(str);
        inorder(root);
    }

    public static int i = 0;
    private static TreeNode createTree(String str) {
        TreeNode root = null;
        char ch = str.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    private static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.println(root.value + " ");
        inorder(root.right);
    }
    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        else if (left != null) return left;//左边不为空，此时就返回左边第一个找到的节点
        else if (right != null) return right;//右边不为空，此时就返回右边第一个找到的节点
        else return null;
    }
    //根据前序遍历和中序遍历构造一颗二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildChildTree(preorder, inorder, 0,
                inorder.length - 1);
    }
    public TreeNode buildChildTree(int[] preorder, int[] inorder,
                                   int begin, int end) {
        if (begin > end) return null;
//        TreeNode root = new TreeNode(preorder[i]);
        int rootIndex = findIndex(inorder, begin, end, preorder[i]);
        i++;
        root.left = buildChildTree(preorder, inorder, begin, rootIndex - 1);
        root.right = buildChildTree(preorder, inorder, rootIndex + 1, end);
        return root;
    }

    private int findIndex(int[] inorder, int begin, int end, int key) {
        for (int j = begin; j <= end; j++) {
            if (inorder[j] == key) return j;
        }
        return -1;
    }

    //根据中序遍历和后序遍历创建一颗二叉树
    /*1.先从后序遍历中找到根，之后在中序遍历中找到根的位置，从后往前遍历字符串，
    * 先创建右子树，后创建左子树*/
    public int a;
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        a = postorder.length - 1;
        return buildChildTree2(inorder, postorder, 0, inorder.length - 1);
    }
    public TreeNode buildChildTree2(int[] inorder, int[] postorder,
                                   int begin, int end) {
        if (begin > end) return null;
//        TreeNode root = new TreeNode(postorder[a]);
        int rootIndex = findIndex(postorder, begin, end, postorder[a]);
        a--;
        root.right = buildChildTree2(inorder, postorder, rootIndex + 1, end);
        root.left = buildChildTree2(inorder, postorder, begin, rootIndex - 1);
        return root;
    }
    //根据前序遍历字符串创建二叉树
    public String tree2str(TreeNode root) {
        if (root == null) return null;
        StringBuilder builder = new StringBuilder();
        tree2strChild(root, builder);
        return builder.toString();
    }

    private void tree2strChild(TreeNode left, StringBuilder builder) {
        if (root == null) return;
        builder.append(root.value);
        if (root.left != null) {//左子树不为空
            builder.append("(");
            tree2strChild(root.left, builder);
            builder.append(")");
        }else {//左子树为空的情况下考虑右子树的情况
            if (root.right != null) {
                builder.append("()");
            }else {
                return;
            }
        }
        if (root.right != null) {
            builder.append("(");
            tree2strChild(root.right, builder);
            builder.append(")");
        }else {
            return;
        }
    }
    //判断一棵树是否为完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(root.left);
                queue.offer(root.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) return false;
        }
        return true;
    }
    //非递归实现前序变
    public List<Character> preorderTraversalNor(TreeNode root) {
        List<Character> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.value);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
    //非递归实现二叉树中序遍历
    public List<Character> inorderTraversalNor(TreeNode root) {
        List<Character> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.value);
            cur = top.right;
        }
        return list;
    }
}











